Цілоцислові задачі лінійног програмування – метод Гоморі
Вирішимо пряму задачу лінійного програмування симплексним методом, з використанням симплексного таблиці.
Визначимо максимальне значення цільової функції F (X) = - 3x1 + 5x2 + 4x3
за таких умов-обмежень.
5x1 + 3x3≤13
4x1 - 2x2 + x3≤7
6x1 + 4x2≤15
Для побудови першого опорного плану систему нерівностей зведемо до системи рівнянь шляхом введення додаткових змінних (перехід до канонічної форми).
В 1-ій нерівності (≤) -вводимо базисну змінну x4. В 2-ій нерівності (≤) - вводимо базисну змінну x5. В 3-ій нерівності (≤) - вводимо базисну змінну x6.
5x1 + 0x2 + 3x3 + 1x4 + 0x5 + 0x6 = 13
4x1-2x2 + 1x3 + 0x4 + 1x5 + 0x6 = 7
6x1 + 4x2 + 0x3 + 0x4 + 0x5 + 1x6 = 15
Матриця коефіцієнтів A = a(ij) цієї системи рівнянь має вигляд:
Базисні змінні це змінні, які входять тільки в одне рівняння системи обмежень і притому з одиничним коефіцієнтом.
Вирішимо систему рівнянь відносно базисних змінних: x4, x5, x6.
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план: X1 = (0, 0, 0, 13, 7, 15)
Базисне рішення називається допустимим, якщо воно невід'ємне.
Переходимо до основного алгоритму симплекс-методу.
Запишемо симплекс-таблицю (Т0)
Базис
B
x1
x2
x3
x4
x5
x6
x4
13
5
0
3
1
0
0
x5
7
4
-2
1
0
1
0
x6
15
6
4
0
0
0
1
F(X0)
0
3
-5
-4
0
0
0
Ітерація № 0.
1. Перевірка критерію оптимальності (правило А).
Поточний опорний план неоптимальний, оскільки в індексному рядку F(X0) наявні від’ємні коефіцієнти:.-5; -4.
2. Визначення нової базисної змінної.
В якості ведучого виберемо стовпець, який відповідає змінній x2, - на це вказує найбільший по модулю від’ємний коефіцієнт: -5 в рядку F(X0).
3. Визначення нової вільної змінної (правило В).
Обчислимо додатні значення Di по рядках як частку від ділення: bi / ai2
і з них виберемо найменше: min (- , - , 15 : 4 ) = 33/4. Отже, 3-ій рядок є вивідним.
Розв’язуючий елемент дорівнює (4) і стоїть на перетині ведучого стовпця і вивідного рядка.
Базис
B
x1
x2
x3
x4
x5
x6
min
x4
13
5
0
3
1
0
0
-
x5
7
4
-2
1
0
1
0
-
x6
15
6
4
0
0
0
1
33/4
F(X1)
0
3
-5
-4
0
0
0
0
4. Перерахунок симплекс-таблиці.
Формуємо наступну частину симплексного таблиці.
Замість змінної x6 в план Т1 увійде змінна x2 .
Рядок, який відповідає змінній x2 в плані Т1, отриманий в результаті поділу всіх елементів даного рядка на розв’язуючий елемент РЕ=4.
На місці розв’язуючого елемента в плані Т1 отримуємо 1, а в інших клітинах стовпця x2 плану Т1 записуємо нулі.
Таким чином, у новому плані Т1 вже маємо заповнені рядок x2 і стовпець x2.
Всі інші елементи нового плану Т1, включаючи елементи індексного рядка, визначаються за правилом прямокутника.
Для цього вибираємо зі старого плану чотири числа, які розташовані в вершинах прямокутника і завжди включають розв’язуючий елемент РЕ.
НЕ = СЕ - (А * В) / РЕ
СТЕ - елемент старого плану, РЕ - розв’язуючий елемент (4), А і В - елементи старого плану, що утворюють прямокутник з елементами СТЕ і РЕ.
Розрахунок кожного елемента приведений у вигляді таблиці:
B
x 1
x 2
x 3
x 4
x 5
x 6
13-(15 • 0):4
5-(6 • 0):4
0-(4 • 0):4
3-(0 • 0):4
1-(0 • 0):4
0-(0 • 0):4
0-(1 • 0):4
7-(15 • -2):4
4-(6 • -2):4
-2-(4 • -2):4
1-(0 • -2):4
0-(0 • -2):4
1-(0 • -2):4
0-(1 • -2):4
15 : 4
6 : 4
4 : 4
0 : 4
0 : 4
0 : 4
1 : 4
0-(15 • -5):4
3-(6 • -5):4
-5-(4 • -5):4
-4-(0 • -5):4
0-(0 • -5):4
0-(0 • -5):4
0-(1 • -5):4
Отримуємо нову симплекс-таблицю (Т1):
Базис
B
x1
x2
x3
x4
x5
x6
x4
13
5
0
3
1
0
0
x5
141/2
7
0
1
0
1
1/2
x2
33/4
11/2
1
0
0
0
1/4
F(X1)
183/4
101/2
0
-4
0
0
11/4
Ітерація № 1.
1. Перевірка критерію оптимальності (правило А).
Поточний опорний план неоптимальний, оскільки в індексному рядку F(X0) наявний від’ємний коефіцієнт.
2. Визначення нової базисної змінної.
В якості ведучого виберемо стовпець, який відповідає змінній x3, оскільки на ...
